package cn.demoncat.util.lang.entity.data;

/**
 * 链表栈 - 无限容量
 * 
 * @author 延晓磊
 *
 * @since 2020年6月28日
 */
public class LinkedStack<E> implements Stack<E> {
	
	// 栈顶/链表头
	private Node<E> top;
	// 栈长
	private int size = 0;
	 
	/**
	 * 构建栈
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月28日
	 */
    public LinkedStack() {
    	super();
    }
    
    /**
     * 是否空栈
     * 
     * @return
     * 
     * @author 延晓磊
     *
     * @since 2020年6月28日
     */
    @Override
    public boolean isEmpty() {
    	return top == null;
    }
    
    /**
     * 入栈
     * 
     * @param e
     * 
     * @author 延晓磊
     *
     * @since 2020年6月28日
     */
    @Override
    public void push(E e) {
    	// 压入栈顶
    	if (isEmpty()) {
			// 空栈
    		top = new Node<>(e, null);
		}else {
			// 单向链表，头部增加
			top = new Node<>(e, top);
		}
		// 计数
		size ++;
    }

    /**
     * 出栈
     * 
     * @return
     * 
     * @throws RuntimeException 栈空
     * 
     * @author 延晓磊
     *
     * @since 2020年6月28日
     */
    @Override
	public E pop() {
    	// 空栈
    	if (isEmpty()) {
			throw EMPTY_EX;
		}
    	// 弹出栈顶
    	E e = top.data;
    	// 删除栈顶/链表头后移
    	top = top.next;
    	size --;
        return e;
    }

    /**
     * 查看栈顶
     * 
     * @return 空栈返回null
     * 
     * @author 延晓磊
     *
     * @since 2020年6月28日
     */
    @Override
	public E peek() {
    	// 空栈
    	if (isEmpty()) {
			return null;
		}
    	// 查看栈顶
		return top.data;
    }
    
    /**
     * 栈长
     * 
     * @return
     * 
     * @author 延晓磊
     *
     * @since 2020年6月28日
     */
    @Override
    public int size() {
    	return size;
    }
    

    /**
     * 打印
     * 
     * @return
     *
     * @author 延晓磊
     *
     * @since 2020年6月28日
     */
	@Override
	public String toString() {
		// 空栈
		if (isEmpty()) {
			return "[]";
		}
		// 栈顶 > 栈底
		Node<E> node = top;
        StringBuilder str = new StringBuilder();
		str.append('[');
		while(true) {
			str.append(node.data);
			// 下一个节点
			node = node.next;
			if (node == null) {
				str.append("]");
				break;
			}else {
				str.append(", ");
			}
		}
        return str.toString();
	}
 
	/**
	 * 节点
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月27日
	 */
	private static class Node<E> {

		// 数据
		private final E data;
		// 下一个节点
		private final Node<E> next;

		private Node(E data, Node<E> next) {
			super();
			this.data = data;
			this.next = next;
		}
	}
    
}
